package leetcode.秋招.五八;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2021/9/25 18:50
 * @description：
 */


public class Solution2 {

    @Test
    public void Test() {
        boolean[] booleans = pathAvailable(new int[][]{{1, 1, 1, 1}, {0, 0, 0, 0}, {1, 1, 1, 1}, {1, 1, 0, 1}},
                new int[][]{{0, 0}, {0, 1}, {2, 0}}, new int[][]{{0, 3}, {2, 2}, {3, 3}});
        System.out.println(Arrays.toString(booleans));
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给出当前的矩阵和起止点列表，求出对应起止点是否可以通行
     * @param matrix int整型二维数组 当前区域的矩阵表示
     * @param starts int整型二维数组 起始点的集合
     * @param ends int整型二维数组 结束点的集合
     * @return bool布尔型一维数组
     */
    private int[][] matrix;
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private boolean[][] isVisited;
    public boolean[] pathAvailable (int[][] matrix, int[][] starts, int[][] ends) {
        // write code here
        this.matrix = matrix;
        if (matrix.length == 0 || matrix[0].length == 0) return new boolean[0];
        boolean[] res = new boolean[starts.length];
        for (int i = 0; i < starts.length; i++) {
            res[i] = isConnect(starts[i], ends[i]);
        }
        return res;
    }

    public boolean isConnect(int[] start, int[] end) {
        this.isVisited = new boolean[matrix.length][matrix[0].length];
        return dfs(start[0], start[1], end[0], end[1]);
    }

    private boolean dfs(int curX, int curY, int endX, int endY) {
        if (curX == endX && curY == endY) return true;
        isVisited[curX][curY] = true;
        boolean flag = false;
        for (int[] dir : dirs) {
            int curXX = curX + dir[0];
            int curYY = curY + dir[1];
            if (curXX >= 0 && curXX < matrix.length
                    && curYY >= 0 && curYY < matrix[0]. length
                    && !isVisited[curXX][curYY]
                    && matrix[curXX][curYY] == 1) {
                flag |= dfs(curXX, curYY, endX, endY);
            }
            if (flag) return true;
        }
        return flag;
    }
}
